//
// This software is now distributed according to
// the Lesser Gnu Public License. Please see
// http://www.gnu.org/copyleft/lesser.txt for
// the details.
// -- Happy Computing!
//
package com.stevesoft.pat;

import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Vector;

/** This class is just like oneChar, but doesn't worry about case. */
class FastChar extends oneChar {

	FastChar(char c) {
		super(c);
	}

	public int matchInternal(int p, Pthings pt) {
		return (p < pt.src.length() && pt.src.charAt(p) == c) ? nextMatch(p + 1, pt) : -1;
	}

	Pattern clone1(Hashtable h) {
		return new FastChar(c);
	}
}

/**
 * This class is a hashtable keyed by Character Objects. It is used to match
 * things of the form (?:a..|b..|c..|..) match with greater efficiency -- by
 * using a Hashtable that indexes into the group of patterns.
 */
class Branch extends Pattern {

	Hashtable h = new Hashtable();
	// We need to keep track of the order
	// of the keys -- if we don't then
	// recompiling the output of toString
	// may produce errors by re-ordering
	// ()'s and changing the id number of
	// the backreference associated with
	// a subpattern.
	Vector keys = new Vector();

	Branch() {
	}

	Pattern clone1(Hashtable x) {
		Branch b = new Branch();
		b.keys = (Vector) keys.clone();
		x.put(this, b);
		x.put(b, b);
		for (int i = 0; i < keys.size(); i++) {
			Pattern p = (Pattern) h.get(keys.elementAt(i));
			b.h.put(keys.elementAt(i), p.clone(x));
		}
		return b;
	}

	// this function eliminates Branches with 0 or 1 elements.
	final Pattern reduce(boolean ignoreCase, boolean dontMinQ) {
		if (h.size() == 1) {
			Enumeration e = h.keys();
			Character c = (Character) e.nextElement();
			Pattern oc;
			if (ignoreCase || dontMinQ)
				oc = new oneChar(c.charValue());
			else
				oc = new FastChar(c.charValue());
			oc.next = (Pattern) h.get(c);
			oc.add(next);
			return oc;
		}
		else if (h.size() == 0)
			return null;
		return this;
	}

	public patInt maxChars() {
		Enumeration e = h.keys();
		patInt count = new patInt(0);
		while (e.hasMoreElements()) {
			Object key = e.nextElement();
			Pattern pa = (Pattern) h.get(key);
			patInt pi = pa.maxChars();
			pi.inc();
			count.maxeq(pi);
		}
		return count;
	}

	public patInt minChars() {
		Enumeration e = h.keys();
		patInt count = new patInt(0);
		while (e.hasMoreElements()) {
			Object key = e.nextElement();
			Pattern pa = (Pattern) h.get(key);
			patInt pi = pa.minChars();
			pi.inc();
			count.mineq(pi);
		}
		return count;
	}

	// adds a oneChar object to this Branch
	void addc(oneChar o, boolean ignoreCase, boolean dontMinQ) {
		Pattern n = o.next;
		if (n == null)
			n = new NullPattern();
		else
			n = RegOpt.opt(n, ignoreCase, dontMinQ);
		n.setParent(this);
		set(new Character(o.c), n, ignoreCase, dontMinQ);
		if (ignoreCase) {
			if (o.c != o.altc)
				set(new Character(o.altc), n, ignoreCase, dontMinQ);
			if (o.c != o.altc2 && o.altc != o.altc2)
				set(new Character(o.altc2), n, ignoreCase, dontMinQ);
		}
	}

	void set(Character c, Pattern n, boolean igc, boolean dontMinQ) {
		Pattern p = (Pattern) h.get(c);
		next = null;
		// This letter is not yet used in the Branch object.
		// We need to add it.
		if (p == null) {
			if (n instanceof Or) {
				// A NullPattern is prepended to an Or
				// to prevent confusing this object.
				// For example: (boo|bug) => (b(?:oo|ug))
				// during this process. However, we
				// want (b(?:oo|ell)|bug)
				NullPattern np = new NullPattern();
				np.add(n);
				h.put(c, np);
			}
			else {
				h.put(c, n);
			}
			// Make sure we remember the order things were
			// added into the Branch object so that we can
			// properly convert it to a String.
			keys.addElement(c);
		}
		else if (p instanceof Or) {
			((Or) p).addOr(n);
		}
		else if (p instanceof oneChar && n instanceof oneChar && ((oneChar) p).c != ((oneChar) n).c) {
			Branch b = new Branch();
			b.addc((oneChar) p, igc, dontMinQ);
			b.addc((oneChar) n, igc, dontMinQ);
			h.put(c, b);
			b.setParent(this);
		}
		else if (p instanceof Branch && n instanceof oneChar) {
			((Branch) p).addc((oneChar) n, igc, dontMinQ);
			n.setParent(p);
		}
		else {
			// Create an Or object to receive the variety
			// of branches in the pattern if the current letter
			// is matched. We do not attempt to make these
			// sub-branches into a Branch object yet.
			Or o = new Or();
			o.setParent(this);
			// Remove NullPattern from p -- it's no longer needed.
			if (p instanceof NullPattern && p.parent == null && p.next != null) {
				o.addOr(p.next);
			}
			else {
				o.addOr(p);
			}
			o.addOr(n);
			Pattern optpat = RegOpt.opt(o, igc, dontMinQ);
			h.put(c, optpat);
			optpat.setParent(this);
		}
	}

	public String toString() {
		StringBuffer sb = new StringBuffer();
		// should protect this...
		sb.append("(?:(?#branch)");// Hashtable)");
		for (int i = 0; i < keys.size(); i++) {
			Character c = (Character) keys.elementAt(i);
			sb.append(c);
			sb.append(h.get(c));
			if (i + 1 < keys.size())
				sb.append("|");
		}
		sb.append(")");
		sb.append(nextString());
		return sb.toString();
	}

	public int matchInternal(int pos, Pthings pt) {
		if (pos >= pt.src.length())
			return -1;
		Pattern n = (Pattern) h.get(new Character(pt.src.charAt(pos)));
		if (n == null)
			return -1;
		if (pt.cbits != null && pt.cbits.get(pos))
			return -1;
		return n.matchInternal(pos + 1, pt);
	}
}

/**
 * This is just a place to put the optimizing function. It is never instantiated
 * as an Object. It just sorts through the RegOpt looking for things it can
 * change and make faster.
 */
public class RegOpt {

	static Pattern opt(Pattern p, boolean ignoreCase, boolean dontMinQ) {
		if (p == null)
			return p;
		if (p instanceof Bracket) {
			Bracket b = (Bracket) p;
			// FastBracket is the only special
			// optimized class to have its own
			// source file.
			p = FastBracket.process(b, ignoreCase);
			// if(!(p instanceof FastBracket)
			// p = Switch.process(b,ignoreCase);
			p.next = b.next;
			p.parent = b.parent;
		}
		else if (p instanceof oneChar && !ignoreCase && !dontMinQ) {
			oneChar o = (oneChar) p;
			p = new FastChar(o.c);
			p.next = o.next;
			p.parent = o.parent;
		}
		else if (p instanceof Or && ((Or) p).leftForm().equals("(?:") && ((Or) p).v.size() == 1) { // Eliminate
																									// this
																									// Or
																									// Object.
			Or o = (Or) p;
			p = (Pattern) o.v.elementAt(0);
			p.setParent(null);
			p = RegOpt.opt(p, ignoreCase, dontMinQ);
			p.add(o.next);
		}
		else if (p instanceof Or) {
			Or o = (Or) p;
			o.pv = null;
			Vector v = o.v;
			o.v = new Vector();
			Branch b = new Branch();
			b.parent = o.parent;
			for (int i = 0; i < v.size(); i++) {
				Pattern pp = (Pattern) v.elementAt(i);
				// We want to have at least two oneChar's in
				// the Or Object to consider making a Branch.
				if (pp instanceof oneChar
						&& (b.h.size() >= 1 || (i + 1 < v.size() && v.elementAt(i + 1) instanceof oneChar)))
					b.addc((oneChar) pp, ignoreCase, dontMinQ);
				else {
					if (b.keys.size() > 0) {
						Pattern p2 = (Pattern) b.reduce(ignoreCase, dontMinQ);
						if (p2 != null) {
							o.addOr(p2);
							b = new Branch();
							b.parent = o.parent;
						}
					}
					o.addOr(opt(pp, ignoreCase, dontMinQ));
				}
			}
			if (b.keys.size() > 0) {
				Pattern p2 = (Pattern) b.reduce(ignoreCase, dontMinQ);
				if (p2 != null)
					o.addOr(p2);
			}
			if (o.v.size() == 1 && o.leftForm().equals("(?:")) { // Eliminate
																	// Or Object
				p = (Pattern) o.v.elementAt(0);
				p.setParent(null);
				p = RegOpt.opt(p, ignoreCase, dontMinQ);
				p.add(o.next);
			}
		}
		else if (p instanceof FastMulti) {
			PatternSub ps = (PatternSub) p;
			ps.sub = RegOpt.opt(ps.sub, ignoreCase, dontMinQ);
		}
		else if (p instanceof Multi && safe4fm(((PatternSub) p).sub)) {
			Multi m = (Multi) p;
			FastMulti fm = null;
			try {
				fm = new FastMulti(m.a, m.b, opt(m.sub, ignoreCase, dontMinQ));
			} catch (RegSyntax rs) {
			}
			fm.parent = m.parent;
			fm.matchFewest = m.matchFewest;
			fm.next = m.next;
			p = fm;
		}
		if (p.next != null)
			p.next = opt(p.next, ignoreCase, dontMinQ);
		return p;
	}

	final static boolean safe4fm(Pattern x) {
		while (x != null) {
			if (x instanceof Bracket)
				;
			else if (x instanceof Range)
				;
			else if (x instanceof oneChar)
				;
			else if (x instanceof Any)
				;
			else if (x instanceof Custom && ((Custom) x).v instanceof UniValidator)
				;
			else if (x instanceof Or) {
				Or o = (Or) x;
				if (!o.leftForm().equals("(?:"))
					return false;
				patInt lo = o.countMinChars();
				patInt hi = o.countMaxChars();
				if (!lo.equals(hi))
					return false;
				for (int i = 0; i < o.v.size(); i++)
					if (!safe4fm((Pattern) o.v.elementAt(i)))
						return false;
			}
			else
				return false;
			x = x.next;
		}
		return true;
	}
	/*
	 * public static void setParents(Regex r) { setParents(r.thePattern,null); }
	 * static void setParents(Pattern p,Pattern x) { if(p instanceof PatternSub &&
	 * !(p instanceof FastMulti) && !(p instanceof DotMulti)) RegOpt.setParents(
	 * ((PatternSub)p).sub, p); else if(p instanceof Or && !(p instanceof
	 * Bracket)) { Or o = (Or)p; for(int i=0;i<o.v.size();i++)
	 * RegOpt.setParents((Pattern)o.v.elementAt(i),o); } else if(p instanceof
	 * Branch) { Branch b = (Branch)p; Enumeration e = b.h.keys();
	 * while(e.hasMoreElements()) { Object o = e.nextElement();
	 * RegOpt.setParents( (Pattern)b.h.get(o), b); } } if(p.next == null)
	 * p.parent = x; else { p.parent = null; RegOpt.setParents(p.next,x); } }
	 */
}
